package com.zhu.solution.stringQuestion;



/*最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：
输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成
*
* */
/**
 * Created with IntelliJ IDEA.
 *
 * @Author: zhujiabao
 * @Date: 2021/12/23/10:32
 * @Description:
 */
public class StringSolution_9 {

    public static void main(String[] args) {

        String[] strs = {"flower","flow","flight"};
//        String[] strs = {"dog","racecar","car"};

        System.out.println(new StringSolution_9().longestCommonPrefix(strs));
        System.out.println(new StringSolution_9().longestCommonPrefix_2(strs));
        System.out.println(new StringSolution_9().longestCommonPrefix_3(strs));
        System.out.println(new StringSolution_9().longestCommonPrefix_4(strs));


    }
    /*用string拼装*/
    public String longestCommonPrefix(String[] strs) {

        int length = strs.length;

        if (strs == null || length == 0)
            return "";

        if (length == 1)
            return strs[0];

        String compareString = "";
        String commonString =strs[0];

        for (int i=1; i<length; i++){
            compareString = commonString;
            commonString = "";
            int minLength = Integer.min(compareString.length(),strs[i].length());
            for (int j=0; j<minLength; j++){
                if (compareString.charAt(j) != strs[i].charAt(j))
                    break;
                commonString = commonString + compareString.charAt(j);
            }

            if (commonString.length() == 0)
                return "";
        }


        return commonString;
    }

    /*用StringBuffer拼装*/
    public String longestCommonPrefix_2(String[] strs) {

        int length = strs.length;

        if (strs == null || length == 0)
            return "";

        StringBuilder compareString ;
        StringBuilder commonString =new StringBuilder(strs[0]);

        for (int i=1; i<length; i++){
            compareString = commonString;
            commonString = new StringBuilder();
            int minLength = Integer.min(compareString.length(),strs[i].length());
            for (int j=0; j<minLength; j++){
                if (compareString.charAt(j) != strs[i].charAt(j))
                    break;
                commonString.append(compareString.charAt(j));
            }
            if (commonString.length() == 0)
                return "";
        }


        return commonString.toString();
    }



    /*别人的代码,用for替换while，差别不大，但用while更好*/
    public String longestCommonPrefix_4(String[] strs) {
        //边界条件判断
        if (strs == null || strs.length == 0)
            return "";
        //默认第一个字符串是他们的公共前缀
        String pre = strs[0];
        for(int i=1; i < strs.length; i++) {
            //不断的截取
            while (strs[i].indexOf(pre) != 0)
                pre = pre.substring(0, pre.length() - 1);

            if(pre.equals(""))
                return "";

        }
        return pre;

    }
    /*别人的代码*/
    public String longestCommonPrefix_3(String[] strs) {
        //边界条件判断
        if (strs == null || strs.length == 0)
            return "";
        //默认第一个字符串是他们的公共前缀
        String pre = strs[0];
        int i = 1;
        while (i < strs.length) {
            //不断的截取
            while (strs[i].indexOf(pre) != 0)
                pre = pre.substring(0, pre.length() - 1);

            if(pre.equals(""))
                return "";

            i++;

        }
        return pre;

    }
}
